Many software systems interpose a caching layer, known simply as a cache, between the source of data and a storage medium used to persist the data such as a magnetic disk. When data is read from or written to the magnetic disk a copy of the data is stored as entry, sometimes referred to as a “cache line”, in the cache. When the data is subsequently accessed, the copy of the data stored in the cache entry can be accessed more quickly from the cache than the magnetic disk because the caching layer is implemented in a faster storage medium such as random access memory (RAM) or a solid state disk (SSD). However, depending on the size of the cache and the size of the data, some cache entries must be periodically removed or “evicted” from the cache.
The set of algorithms that determine which cache entries should be removed from the cache are called eviction algorithms. One subset of cache eviction algorithms operates by segregating cache entries into two lists: 1) a recency list and 2) a frequency list. The recency list contains cache entries based on how recently the data was accessed. This type of list is commonly referred to a least recently used (LRU) cache because when the cache is full, the least recently accessed cache entries are evicted to make space for cache entries that have been accessed more recently. The frequency list contains cache entries based on how often the cache entries are accessed. This type of list is commonly referred to a least frequently used (LFU) cache because when the cache is full, the least frequently accessed cache entries are evicted to make space for data that have been accessed more recently.
In some cache eviction algorithm implementations, when data is stored in the cache, it is first stored as a cache entry in the LRU cache. If the data is subsequently accessed even one more time, it is them moved or “promoted” from the LRU cache to the LFU cache. Eventually, the cache entry may be evicted from the cache altogether because it has been removed from both LFU and LRU caches. When the size of cache entries is very large almost all cache entries are promoted from the LRU cache to the LFU cache resulting in the LRU cache being nearly empty while filling up the LFU cache to the point where cache entries will be evicted from the cache entirely.